1. Field of the Invention
The invention relates to digital communication, and more specifically to Radio Frequency Identification (RFID).
2. Description of the Related Art
Advances in supply-chain technologies are promoting the rapid deployment of RFID tags to identify individual items, such as passports, retails products, books, or even humans.
FIG. 1 is a block diagram of conventional RFID system 100. RFID system 100 comprises reader 110 and one or more RFID tags 130 that are within the interrogation zone 120 of reader 110.
Reader 110 comprises an antenna 112, a processor 114, and a memory 116. A typical tag 130 comprises (i) an antenna 132, (ii) a memory 136, and (iii) a processor 134 for rudimentary calculations. FIG. 1 shows details for only one tag, but each tag comprises the same components. A typical tag contains within its memory a unique 12-digit hexadecimal tag identifier (tag ID), comprising an 8-digit hexadecimal category code (i.e., category ID) and a unique 4-digit hexadecimal instance within that category. For example, a particular tag ID value might be 048AF742C12D, where 048AF742 is the category ID value, and C12D is the unique instance value for that category ID value. Whereas the tag ID value is meant to be unique, multiple tags can have the same category ID value.
A typical use of system 100 is to determine which tags, and hence, which objects are within the system. This determination is made by performing an interrogation. For a time duration known as a frame, reader 110 emits from antenna 112 a downlink signal, which energizes tags 130 within interrogation zone 120. Also within the frame duration, each energized tag 130 transmits an uplink signal back to reader 110. A typical uplink signal contains the tag ID value. Reader 110 collects and collates the received tag IDs and generates a list of which tag IDs are in the system.
A potential problem with the interrogation procedure is collisions, i.e., when two or more tags transmit at the same time. A reader that receives a collision typically cannot determine how many tags transmitted to generate the collision, or which tags transmitted to generate the collision. As such, the reader cannot state with certainty which tags are in the system.
One protocol, called framed slotted ALOHA, reduces collisions by dividing the frame into a number M of equal-sized slots, where each slot has a time duration long enough for a tag to transmit the information requested, e.g., the tag ID. The number M of slots in a frame is also referred to as the frame size M.
At the start of a frame, the reader sends two pieces of information to the tags: the frame size M and a seed value R. Each tag's integrated circuit is capable of implementing a tag algorithm (e.g., a uniform hash function) that takes the seed value R, the frame size M, and the tag ID, and generates a pseudo-random slot index number. Each tag transmits its tag ID during the slot corresponding to its generated slot index number. Depending on the tag algorithm, the algorithm's input parameters, and the different tags are that present in the system, a tag may be the only tag transmitting in its slot or the tag's slot may correspond to a collision, in which the tag and one or more other tags transmit their tag IDs at the same time. When a tag is the only tag transmitting in its slot, then the reader is able to identify that tag as being present. When a collision occurs in a slot, the reader is unable to identify the particular tags transmitting during that slot.
If the reader detects one or more collisions, then the reader selects a different seed value R and starts another frame. Because the seed R is different, the tags will generate a different pseudo-random set of slots in which to transmit, such that tags that previously collided with other tags might not collide in the current frame.
Frames are performed until all tags have been identified, or the process is terminated by some specified threshold, such as a maximum number of frames. The total number of performed frames is denoted r. The total number of slots in all the performed frames is known as the scan length in. Thus, m=r·M. The one or more frames used to identify the tags in the system may be referred to as corresponding to a single interrogation of the system.
The example given above focused on determining the particular tag IDs that are present in a system. However, some applications might need to know only the categories of products that are present in the system without having to identify each different product. For such applications, it may be sufficient to identify only the different category IDs for the tags that are present in the system, as opposed to identifying the particular tags IDs.